from random import shuffle, randint, choice
import re
import time
from pprint import pprint

#
# Test Cases
#
test_cases = [
	# (unsorted list, sorted list)
	(list('bca'), ['a', 'b', 'c']),
	(list('CbA'), ['A', 'b', 'C']),
	(list('r0B9a'), ['a', 'B', 'r', '0', '9']),
	(['a2', '1a', '10a', 'a1', 'a100'], ['a1', 'a2', 'a100', '1a', '10a']),
	(['GAM', 'alp2', 'ALP11', '1', 'alp100', 'alp10', '100', 'alp1', '2'],
		['alp1', 'alp2', 'alp10', 'ALP11', 'alp100', 'GAM', '1', '2', '100']),
	(list('ra0b9A'), ['A', 'a', 'b', 'r', '0', '9']),
	(['Abc', 'abc', 'ABc'], ['ABc', 'Abc', 'abc']),
]

#
# Sort Functions
#
def sorted_insensitive(unsorted_list):
	return sorted(unsorted_list, key=lambda s: s.lower())
	
def sorted_natural(unsorted_list):
	"""see http://stackoverflow.com/a/4836734/1093087"""
	convert = lambda text: int(text) if text.isdigit() else text.lower() 
	alphanum_key = lambda key: [convert(c) for c in re.split('([0-9]+)', key)] 
	return sorted(unsorted_list, key=alphanum_key)

def alpha_before_numeric(unsorted_list):
	ord_shift = lambda c: c.isdigit() and chr(ord('z') + int(c.lower()) + 1) or c.lower()
	adjust_word = lambda word: "".join([ord_shift(c) for c in list(word)])
	
	def cmp_(a, b):
		return cmp(adjust_word(a), adjust_word(b))

	return sorted(unsorted_list, cmp_)

def alpha_before_numeric_natural(unsorted_list):
	"""splice each string into tuple like so:
	'abc100def' -> ('a', 'b', 'c', 100, 'd', 'e', 'f') ->
	(ord('a'), ord('b'), ord('c'), ord('z') + 1 + 100, ...) then compare
	each tuple"""
	re_p = "([0-9]+|[A-za-z])"
	ordify = lambda s: ord('z') + 1 + int(s) if s.isdigit() else ord(s.lower())
	str_to_ord_tuple = lambda key: [ordify(c) for c in re.split(re_p, key) if c]
	return sorted(unsorted_list, key=str_to_ord_tuple)

def alpha_before_numeric_natural_sensitive(unsorted_list):
	"""presorting the list should work because python sorted stable sorts;
	see http://wiki.python.org/moin/HowTo/Sorting/#Sort_Stability_and_Complex_Sorts"""
	presorted_list = sorted(unsorted_list)
	return alpha_before_numeric_natural(presorted_list)
	
def ransom_sort(unsorted_list):
	"""http://stackoverflow.com/a/12185223/1093087"""
	re_natural = re.compile('[0-9]+|[^0-9]+')

	def natural_key(s):
		return [(1, int(c)) if c.isdigit() else (0, c.lower()) \
			for c in re_natural.findall(s)] + [s]
		
	return sorted(unsorted_list, key=natural_key)


#
# Test Apparatus
#
sort_funcs = [
	sorted,
	sorted_insensitive,
	sorted_natural,
	alpha_before_numeric,
	alpha_before_numeric_natural,
	alpha_before_numeric_natural_sensitive,
	ransom_sort,
]

def test_sort():
	for sort_func in sort_funcs:
		print "\n\nSORT FUNC: %s" % (sort_func)
		failed = False
		
		for unsorted_list, expect in test_cases:            
			try:
				sorted_list = sort_func(unsorted_list)
				assert sorted_list == expect
				print '[pass] sorted list as expected: %s -> %s == %s' % (
					unsorted_list, sorted_list, expect)
			except AssertionError:
				failed = True
				print '[fail] failed to sort list as expected: %s -> %s != %s' % (
					unsorted_list, sorted_list, expect)
				break
		
		if not failed:  
			print "SUCCESS: func %s succeeded" % (sort_func)
		else:
			print "FAIL: func %s failed" % (sort_func)
		
def test_performance():
	# test params
	trials = 1000
	list_len = 1000
	test_funcs = [
		sorted,
		alpha_before_numeric_natural_sensitive,
		ransom_sort,
	]
	
	# build test datasets
	def rand_str():
		chars = list('abcdefABCDEF0123456789')
		str_len = randint(4,10)
		return ''.join([choice(chars) for n in range(str_len)])
	
	lists_to_sort = []
	for n in range(trials):
		list_to_sort = []
		for n in range(list_len):
			list_to_sort.append(rand_str())
		lists_to_sort.append(list_to_sort)
		
	# run trials
	results = []
	for sort_func in test_funcs:
		
		t0 = time.time()
		
		for unsorted_list in lists_to_sort:
			sorted_list = sort_func(unsorted_list)
	
		total_time = time.time() - t0
		per_trial = total_time / n
		
		result = (
			sort_func,
			per_trial,
			total_time,
			trials
		)
		results.append(result)
	
	# sort results
	sorted_results = sorted(results, key=lambda row: row[1])
	
	# print
	print "\n\n\nPERFORMANCE:"
	pprint(sorted_results)

		
if __name__ == "__main__":
	test_sort()
	test_performance()